augmented_containers::​augmented_deque_t

template<
	typename element_t,
	typename allocator_t = std::allocator<element_t>,
	typename requested_stride_to_projector_and_accumulator_map_t = std::tuple<>
> struct augmented_deque_t;

augmented_deque_t is an augmented, strictly double-ended queue. It's part of the augmented containers library, providing a stronger version of sequence containers (let containers (and possibly its subranges) always have several accompanying results of algorithms/views), as well as <algorithm> and <ranges> (when the input sequence changes, refresh output values/ranges in logarithmic time complexity).

• An augmented_deque_t has at least one sub-sequences, each having a compile-time or run-time specified stride (if run-time specified, can be adjusted at any time, although does not affect grouping of already enququed elements), an optional projector and an optional accumulator. Container elements are shared between all sub-sequences and are stored in sub-sequence 0. In every subsequence, every neighboring stride elements are projected into a projected result (if stride is compile-time specified and equals to 1, this step can be skipped), then accumulated into an accumulated result (this step can also be skipped if you only need the projected result; on sub-sequences other than sub-sequence 0 whose stride is compile-time specified and equals to 1, it's meaningless to skip both projection and accumulation steps and thus is not allowed).
• augmented_deque_t allows range update: first modify some elements, then call update_range to refresh the projected results and accumulated results that covers those elements in O(distance(range)+lg(N)) time (as elements are organized in prefect binary trees, the number of most of the internal nodes to be updated is O(distance(range))). A common mistake would be to forget to call update_range.
• augmented_deque_t allows subrange query: call read_range to collect projected results and accumulated results that covers the range in O(lg(distance(range))) time. If the accumulated result is a range instead of a single value, the result is probably formed by projected results linking to each other, in this case you should not call read_range because there are no more pointers left for you to form another range (see examples below for an intuitive feel).
• augmented_deque_t does not allow inserting or removing elements in the middle. Having this restriction allows it to privide the striding functionality (which the more general augmented_sequence_t can not provide.)

Complexity Table

How to achieve O(1) enqueue && O(1) dequeue && O(lg(N)) accumulation depth?

augmented_deque_t is a node-based container. First the element nodes forms a doubly linked list, then tree nodes organize them into prefect binary trees. The enqueue and dequeue operations are analogous to operator++ and operator-- in binary positional numeral system.

• When enqueue operations comes consecutively, the most frequent operation is new tree_node_t whose number is equal to the number of internal nodes in perfect binary trees which is less than the number of elements. (Carrying at position $i$ ($i\in \mathbb{N}$) happens every $2^i$ enqueue operations, so every enqueue operation pays $\frac{1}{2^i}$ points of energy for each position $i$ (O(1) points of energy for all positions in sum).)
• When dequeue operations comes consecutively, the most frequent operation is delete p_tree_node whose number is equal to the number of internal nodes in perfect binary trees which is less than the number of elements.
• When enqueue and dequeue operations comes alternately, in order to prevent cascading carrying and borrowing between numbers like 0b01111111 and 0b10000000, a modified binary positional numeral system which allows each position to be 0, 1 or 2, is used:

... and note that in the implementation it's double ended (the most significant bit is in the middle and shared by the front part and the back part). The accumulation direction is from the middle digit to both ends (the accumulator should be able to accumulate up to 3 (instead of 2) values at a time, e.g. for each digit node on the right, calculate sum of values from its prev digit node, from its left tree root and from its right tree root), then accumulate the ends together yielding the overall accumulated result of the whole container. That's why updating a element at (near) either end and refreshing the accumulated results only takes O(1).

Examples

The untagged pointers are drawn as solid lines. The 0b1-tagged pointers are drawn as dashed lines.

In each sub-sequence, the digit nodes are organized into a circular doubly linked list. Pointers from/to the end node are 0b1-tagged. The end node's next, middle, prev and accumulated_storage are drawn separately to not break graphviz's layout.

In each digit node's each tree, the tree nodes are organized into a perfect binary tree. The pointer from the root tree node to digit node and pointers from leaf tree nodes to list nodes are 0b1-tagged.

In each sub-sequence, the list nodes are organized into a circular doubly linked list. Pointers from/to the end node are 0b1-tagged. The end node is not drawn to not break graphviz's layout.

empty

The projection and accumulation steps are skipped. What's left can be seen as a std::vector/std::deque that never invalidates iterators/references/pointers, or a std::list with random access ability.

augmented_containers::augmented_deque_t<
	char,
	std::allocator<char>
> augmented_deque;

accumulator_only_yield_one_value_string

The projection step is skipped. element_t(char)s are accumulated into accumulated_storage_t(std::string)s.

augmented_containers::augmented_deque_t<
	char,
	std::allocator<char>,
	std::tuple<
		std::pair<std::integral_constant<std::size_t, 1>, augmented_containers::augmented_deque_helpers::example_stride1_chunk1_projector_skipped_and_accumulator_sequence_t<char, std::string>>
	>
>

projector_and_accumulator_yield_one_value_int

• Sub-sequence 0: the projection step is skipped; accumulator is int operator+(int, int).
• Sub-sequence 1: every 3 element_t(int)s are projected into their std::ranges::max_element, then accumulated into their std::ranges::min.

augmented_containers::augmented_deque_t<
	int,
	std::allocator<int>,
	std::tuple<
		std::pair<std::integral_constant<std::size_t, 1>, augmented_containers::augmented_deque_helpers::example_stride1_chunk1_projector_skipped_and_accumulator_plus_t<int>>,
		std::pair<std::integral_constant<std::size_t, 3>, augmented_containers::augmented_deque_helpers::example_chunkgt1_projector_max_element_and_accumulator_min_t<int>>
	>
> augmented_deque;

projector_and_accumulator_yield_one_value_string

• Sub-sequence 0: the projection step is skipped; accumulator is std::string operator+(std::string const&, std::string const&).
• Sub-sequence 1: every 3 element_t(std::string)s are projected into their std::ranges::max_element, then accumulated into their std::ranges::min.

augmented_containers::augmented_deque_t<
	std::string,
	std::allocator<std::string>,
	std::tuple<
		std::pair<std::integral_constant<std::size_t, 1>, augmented_containers::augmented_deque_helpers::example_stride1_chunk1_projector_skipped_and_accumulator_plus_t<std::string>>,
		std::pair<std::integral_constant<std::size_t, 3>, augmented_containers::augmented_deque_helpers::example_chunkgt1_projector_max_element_and_accumulator_min_t<std::string>>
	>
> augmented_deque;

projector_and_accumulator_yield_multiple_values

• Sub-sequence 0: the projection and accumulation steps are skipped.
• Sub-sequence 1: every 3 element_t(int)s are projected into their std::ranges::stable_sort (stores addresses so you can modify the original elements), then accumulated into their std::ranges::merge | std::views::take(3) (stores addresses so you can modify the original elements).

augmented_containers::augmented_deque_t<
	int,
	std::allocator<int>,
	std::tuple<
		//std::pair<std::integral_constant<std::size_t, 3>, projector_and_accumulator_min_n_element_t<int, 3>>, //commented one of the sub-sequences because it looks messy when there are three images stacked together
		std::pair<std::integral_constant<std::size_t, 3>, projector_and_accumulator_min_n_element_t<int, 3, true>>
	>
> augmented_deque;

projector_and_accumulator_yield_one_view

Each element_t(int) is projected into the navigator portion (prev and next pointers) to be ready to form a circular doubly linked list. The accumulator takes chunk-begins (std::ranges::prev(it).is_end() || (*std::ranges::prev(it) < 50) != (*it < 50)), discards non-chunk-begins (and takes other accumulated circular doubly linked lists), accumulates them into a circular doubly linked lists representing std::ranges::chunk_by_view of the original sequence.

augmented_containers::augmented_deque_t<
	int,
	std::allocator<int>,
	std::tuple<
		std::pair<std::integral_constant<std::size_t, 1>, projector_and_accumulator_diffing_adjacent_element_t>
	>
> augmented_deque;

projector_and_accumulator_yield_multiple_views

Similar to the projector_and_accumulator_yield_one_view example, except that each accumulated_storage_t is "a map from element % 3 to circular doubly linked list's end node" (instead of just "one end node"). The result represents C++32's std::ranges::group_by_view of the original sequence (navigator_style = std::ranges::group_by_view::navigator_style_t::circular_doubly_linked_list, map_container_tt = std::map).

augmented_containers::augmented_deque_t<
	int,
	std::allocator<int>,
	std::tuple<
		std::pair<std::integral_constant<std::size_t, 1>, projector_and_accumulator_group_by_t>
	>
> augmented_deque;

find_by_monotonic_predicate

Each element_t(std::string) is projected into its .size(); accumulator is std::size_t operator+(std::size_t, std::size_t). Use .find_by_monotonic_predicate([&](){ ... }) to find the first element where the accumulated_storage_t(std::size_t) (accumulated string size so far) starts to be greater than the given character index, i.e., the element that contains the the given character indexth character. Note that the hierarchical structure saves time by skiping substructures that don't contain the results.

augmented_containers::augmented_deque_t<
    std::string,
    std::allocator<std::string>,
    std::tuple<
        std::pair<std::integral_constant<std::size_t, 1>, augmented_containers::augmented_deque_helpers::projector_and_accumulator_wrapping_projecting_and_accumulating_functors_t<projecting_n_ary_functor_string_to_length_t, augmented_containers::augmented_deque_helpers::accumulating_binary_functor_wrapping_homogeneous_binary_functor_t<std::size_t, std::plus<std::size_t>>>>
	>
> augmented_deque;

find_by_heap_predicate

The projection step is skipped. element_t(int)s are accumulated into their std::ranges::max. Use .find_by_heap_predicate(itps_output, [&](){ ... }) to eagerly find all elements greater than or equal to the given threshold. Note that the hierarchical structure saves time by skiping substructures that don't contain the results. It's possible to parallelize the search, depending on the availability of std::execution.

augmented_containers::augmented_deque_t<
    int,
    std::allocator<int>,
    std::tuple<
        std::pair<std::integral_constant<std::size_t, 1>, augmented_containers::augmented_deque_helpers::projector_and_accumulator_wrapping_projecting_and_accumulating_functors_t<void, augmented_containers::augmented_deque_helpers::accumulating_binary_functor_wrapping_homogeneous_binary_functor_t<int, augmented_containers::augmented_deque_helpers::max_t<int>>>>
	>
> augmented_deque;

find_by_heap_predicate_generator

Each element_t(std::pair<std::int64_t, std::int64_t>) is projected into its .second (upper endpoint), then accumulated into their std::ranges::max. Use .find_by_heap_predicate_generator([&](){ ... }) to lazily iterate through elements whose upper endpoints are greater than or equal to the given interval's lower endpoint, until lower endpoint is greater than the given interval's upper endpoint, i.e., the elements that intersect with the given interval. Note that the hierarchical structure saves time by skiping substructures that don't contain the results. It's possible to parallelize the search, depending on the availability of std::execution.

augmented_containers::augmented_deque_t<
    std::pair<std::int64_t, std::int64_t>,
    std::allocator<std::pair<std::int64_t, std::int64_t>>,
    std::tuple<
        std::pair<std::integral_constant<std::size_t, 1>, augmented_containers::augmented_deque_helpers::projector_and_accumulator_wrapping_projecting_and_accumulating_functors_t<projecting_n_ary_functor_interval_to_upper_endpoint_t, augmented_containers::augmented_deque_helpers::accumulating_binary_functor_wrapping_homogeneous_binary_functor_t<int, augmented_containers::augmented_deque_helpers::max_t<std::int64_t>>>>
	>
> augmented_deque;

Relationship with <algorithm> and <ranges>

The table shows the constructs that augmented_deque_t provides a stronger replacement of and the constructs that are not relevant and the reasons.

Function Members

Constructors, Assignments, Swap and Destructor

(To scroll horizontally, press and hold down the shift key and scroll the mouse.)

augmented_deque_t();

p = create_and_link_end_nodes()

explicit augmented_deque_t(
	allocator_element_t const &allocator_element);

void clear() &;

pop_back() until empty()

explicit augmented_deque_t(
	size_type count,
	allocator_element_t const &allocator_element = allocator_element_t());

p = create_and_link_end_nodes()
emplace_back() count elements

explicit augmented_deque_t(
	size_type count,
	element_t const &value,
	allocator_element_t const &allocator_element = allocator_element_t());

void assign(
	size_type count,
	element_t const &value) &;

pop_back() until empty()
emplace_back() count elements

template<
	std::input_iterator iterator_t,
	std::sentinel_for<iterator_t> sentinel_t>
augmented_deque_t(
	iterator_t iterator,
	sentinel_t sentinel,
	allocator_element_t const &allocator_element = allocator_element_t());

p = create_and_link_end_nodes()
emplace_back() range's elements

template<
	std::input_iterator iterator_t,
	std::sentinel_for<iterator_t> sentinel_t>
void assign(
	iterator_t iterator,
	sentinel_t sentinel) &;

pop_back() until empty()
emplace_back() range's elements

augmented_deque_t(
	std::initializer_list<element_t> initializer_list,
	allocator_element_t const &allocator_element = allocator_element_t());

p = create_and_link_end_nodes()
emplace_back() initializer_list's elements

augmented_deque_t &operator=(
	std::initializer_list<element_t> initializer_list) &;

pop_back() until empty()
emplace_back() initializer_list's elements

void assign(
	std::initializer_list<element_t> initializer_list) &;

augmented_deque_t(
	augmented_deque_t const &other);

p = create_and_link_end_nodes()
emplace_back() other's elements

augmented_deque_t(
	augmented_deque_t const &other,
	std::type_identity_t<allocator_element_t> const &allocator_element);

augmented_deque_t &operator=(
	augmented_deque_t const &other) &;

pop_back() until empty()

	

		

			

			
propagate_on_container_copy_assignment
		
		

			
false
			
true
		
	
	

		

			
this->allocator_element
and
other.allocator_element
			
==
			
/
			
/
		
		

			
!=
			
/
			
destroy_end_nodes(p)
this->allocator_element = other.allocator_element
p = create_and_link_end_nodes()
		
	
emplace_back() other's elements

augmented_deque_t(
	augmented_deque_t &&other);

this->p = other.p
other.p = create_and_link_end_nodes()
(: allocator_element(move(other.allocator_element)) happens at the end)

augmented_deque_t(
	augmented_deque_t &&other,
	std::type_identity_t<allocator_element_t> const &allocator_element);

	

		

			
allocator_element
and
other.allocator_element
			
==
			
this->p = other.p
other.p = create_and_link_end_nodes()
		
		

			
!=
			
this->p = create_and_link_end_nodes()
emplace_back(move()) other's elements
(other.size() is not changed)
		
	

augmented_deque_t &operator=(
	augmented_deque_t &&other) &;

pop_back() until empty()

	

		

			

			
propagate_on_container_move_assignment
		
		

			
false
			
true
		
	
	

		

			
this->allocator_element
and
other.allocator_element
			
==
			
swap(this->p, other.p)
		
		

			
!=
			
emplace_back(move()) other's elements
(other.size() is not changed)
			
destroy_end_nodes(p)
this->allocator_element = move(other.allocator_element)
p = create_and_link_end_nodes()
swap(this->p, other.p)
		
	

void swap(
	augmented_deque_t &other);

	

		

			

			
propagate_on_container_swap
		
		

			
false
			
true
		
	
	

		

			
this->allocator_element
and
other.allocator_element
			
==
			
swap(this->p, other.p)
		
		

			
!=
			
augmented_deque_t temp_this(other, this->allocator_element)
augmented_deque_t temp_other(*this, other.allocator_element)
swap(this->p, temp_this.p)
swap(other.p, temp_other.p)
			
swap(this->allocator_element, other.allocator_element)
swap(this->p, other.p)
		
	

~augmented_deque_t();

pop_back() until empty()
destroy_end_nodes(p)